2017-07-25

noip模拟赛2017.7.25

Thinking Bear #1

——NOIP 2014 提高组模拟赛

竞赛时间：2014 年 8 月 17 日 18:30－22:00

中文题目名称	拆地毯	还教室	皇后游戏
英文题目名称	carpet	classroom	game
每个测试点时限	1 秒	1 秒	1 秒
内存限制	512MB	512MB	512MB
测试点数目	10	20	20
每个测试点分值	10	5	5
是否有部分分	否	否	否
题目类型	传统型	传统型	传统型

注意：最终测试时，将开启-O2 优化开关。

Thinking Bear #1 拆地毯

【引子】

还记得 NOIP 2011 提高组 Day1 中的铺地毯吗？时光飞逝，光阴荏苒，三年过去了。组织者精心准备的颁奖典礼早已结束，留下的则是被人们踩过的地毯。请你来解决类似于铺地毯的另一个问题。

【问题描述】

会场上有 n 个关键区域，不同的关键区域由 m 条无向地毯彼此连接。每条地毯可由三个整数 u、v、w 表示，其中 u 和 v 为地毯连接的两个关键区域编号， w 为这条地毯的美丽度。由于颁奖典礼已经结束，铺过的地毯不得不拆除。为了贯彻勤俭节约的原则，组织者被要求只能保留 K 条地毯，且保留的地毯构成的图中，任意可互相到达的两点间只能有一种方式互相到达。换言之，组织者要求新图中不能有环。现在组织者求助你，想请你帮忙算出这 K 条地毯的美丽度之和最大为多少。

【输入格式】

第一行包含三个正整数 n、m、K。接下来 m 行中每行包含三个正整数 u、v、w。

【输出格式】

只包含一个正整数，表示这 K 条地毯的美丽度之和的最大值。

【样例输入】

5 4 3
1 2 10
1 3 9
2 3 7
4 5 3

【样例输出】

【样例说明】

选择第 1、2、4 条地毯，美丽度之和为 10 + 9 + 3 = 22。若选择第 1、2、3 条地毯，虽然美丽度之和可以达到 10 + 9 + 7 = 26，但这将导致关键区域 1、2、3 构成一个环，这是题目中不允许的。
Thinking Bear #1 拆地毯
第 3 页共 8 页

【数据规模与约定】

所有测试点的数据规模如下：

保证至少存在一种方案使得在原图中可以选出K条边，这K条边构成的新图环。

Solution

很裸的最大生成树保证选满k条边就不用担心了….

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;
int n,m,k,fa[100100];
struct node{
	int a,b,w;
}e[100100];
bool cmp(node a,node b){
	return a.w>b.w;
}
int findf(int x){
	if(fa[x]==x)return x;
	else return fa[x]=findf(fa[x]);
}
int main()
{
	freopen("carpet.in","r",stdin);
	freopen("carpet.out","w",stdout);
	scanf("%d%d%d",&n,&m,&k);
	for(register int i=1;i<=n;i++){fa[i]=i;}
	for(register int i=1;i<=m;i++)
		scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].w);
	sort(e+1,e+1+m,cmp);
	int cc=1,ans=0;
	while(k)
	{
		int from=e[cc].a,to=e[cc].b,w=e[cc].w;
		int fa_from=findf(from);
		int fa_to=findf(to);
		if(fa_from!=fa_to)
		{
			ans+=w;
			fa[fa_from]=fa_to;
			k--;
		}
		cc++;
	}
	printf("%d",ans);
	return 0;
} 
/*
5 4 3
1 2 10 
1 3 9 
2 3 7 
4 5 3 
*/

Thinking Bear #1 还教室

【引子】

还记得 NOIP 2012 提高组 Day2 中的借教室吗？时光飞逝，光阴荏苒，两年过去了，曾经借教室的同学们纷纷归还自己当初租借的教室。请你来解决类似于借教室的另一个问题。

【问题描述】

在接受借教室请求的 n 天中，第 i 天剩余的教室为 ai个。作为大学借教室服务的负责人，你需要完成如下三种操作共 m 次： ① 第 l 天到第 r 天，每天被归还 d 个教室。 ② 询问第 l 天到第 r 天教室个数的平均数。 ③ 询问第 l 天到第 r 天教室个数的方差。

【输入格式】

第一行包括两个正整数 n 和 m，其中 n 为借教室的天数，m 为操作次数。接下来一行，共包含 n 个整数，第 i 个整数表示第 i 天剩余教室数目为 ai个。接下来 m 行，每行的第一个整数为操作编号（只能为 1 或 2 或 3），接下来包含两个正整数 l 和 r，若操作编号为 1，则接下来再包含一个正整数 d。

【输出格式】

对于每个操作 2 和操作 3，输出一个既约分数（分子与分母互质）表示询问的答案（详见样例）。若答案为 0 ，请输出“0/1”（不含引号）。
【样例输入】
5 4 1 2 3 4 5 1 1 2 3 2 2 4 3 2 4 3 1 5

【样例输出】

4/1 2/3 14/25
Thinking Bear #1 还教室
第 5 页共 8 页

【样例说明】

【数学小贴士】

【数据规模与约定】

所有测试点的数据规模如下：

对于全部测试数据满足：1 ≤ l ≤ r ≤ n，0 ≤ ai ≤ 10，1 ≤ d ≤ 3，操作 1 的数量不超过 10%。注意：ai和 d 的范围很小及操作 1 数量很少的原因是为了保证答案的分子不会很大，以防止答案的分子溢出 64 位整数的范围，这与题目做法无关。

Solution

很裸的线段树，这些题的题面都很迷，贼尴尬的背景，既然是分数输出，那么我们肯定不是直接对答案进行维护，第一问好说仅维护一个区间和，而第二问
我们可以推推公式：
d代表的是区间加值，代表的是区间长度
$\sum_{i=1}^{n} (x_i+d)^{2}=\sum_{i=1}^{n} x_i^{2}+\sum_{i=1}^{n} x_i +d^{2}*n\\$
$\frac{\sum_{i=1}^{n}(x_i-\bar{x})^{2}}{n}=\frac{n*\sum_{i=1}^{n} x_i^{2}-(\sum_{i=1}^{n}x_i)^2}{n^{2}}$
而观察到我们已经维护了区间的求和，那么再维护一个平方和就可以了QAQ

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define LL long long
using namespace std;
int n,q;
struct node{
	int l,r;
	LL s1,s2,d;
}T[400100];
inline int read(){
    char c=getchar();int rtn=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){rtn=rtn*10+c-'0';c=getchar();}
    return rtn*f;
}
void Build_Tree(int p,int l,int r){
	T[p].l=l,T[p].r=r;
	if(l==r)return;
	int mid=(l+r)>>1;
	Build_Tree(p<<1,l,mid);
	Build_Tree(p<<1|1,mid+1,r);
}
inline void deal(int p,int c){
	int ll=T[p].l,rr=T[p].r; 
	T[p].d+=c;
	T[p].s2=T[p].s2+(rr-ll+1)*c*c+2*c*T[p].s1;
	T[p].s1=T[p].s1+(rr-ll+1)*c;
}
inline void pushdown(int p)
{
	int ls=p<<1,rs=p<<1|1;
	deal(ls,T[p].d);deal(rs,T[p].d);
	T[p].d=0;
}
inline void pushup(int p){
	T[p].s1=T[p<<1].s1+T[p<<1|1].s1;
	T[p].s2=T[p<<1].s2+T[p<<1|1].s2;
}
void update(int p,int l,int r,int c){
	int ll=T[p].l,rr=T[p].r;
	if(ll==l&&rr==r)
	{
		deal(p,c);
		return;
	}
	pushdown(p);
	int mid=(ll+rr)>>1;
	if(r<=mid)update(p<<1,l,r,c);
	else if(l>mid)update(p<<1|1,l,r,c);
	else{
		update(p<<1,l,mid,c);
		update(p<<1|1,mid+1,r,c);
	}
	pushup(p);
}
LL query_aven(int p,int l,int r){
	int ll=T[p].l,rr=T[p].r;
	if(ll==l&&rr==r)return T[p].s1;
	pushdown(p);
	int mid=(ll+rr)>>1;
	if(r<=mid)return query_aven(p<<1,l,r);
	else if(l>mid)return query_aven(p<<1|1,l,r);
	else{
		return query_aven(p<<1,l,mid)+
		       query_aven(p<<1|1,mid+1,r);
	}
}
LL query_cha(int p,int l,int r){
	int ll=T[p].l,rr=T[p].r;
	if(ll==l&&rr==r)return T[p].s2;
	pushdown(p);
	int mid=(ll+rr)>>1;
	if(r<=mid)return query_cha(p<<1,l,r);
	else if(l>mid)return query_cha(p<<1|1,l,r);
	else{
		return query_cha(p<<1,l,mid)+
		       query_cha(p<<1|1,mid+1,r);
	}
}
LL gcd(LL a,LL b){
	if(b==0)return a;
	else return gcd(b,a%b);
}
void print(LL x,LL y){
	LL gcd_div=gcd(x,y);
	LL o1=x/gcd_div,o2=y/gcd_div;
	printf("%lld/%lld\n",o1,o2);
}
int main()
{
	freopen("classroom.in","r",stdin);
	freopen("classroom.out","w",stdout);
	scanf("%d%d",&n,&q);
 	Build_Tree(1,1,n);
	for(register int i=1;i<=n;i++){int x=read();update(1,i,i,x);}
	while(q--)
	{
		int opt=read(),from=read(),to=read();
		if(opt==1)
		{
			int cc=read();
			update(1,from,to,cc);
			continue;
		}
		if(opt==2)
		{
			LL ans=query_aven(1,from,to),len=to-from+1;
			print(ans,len);
			continue;
		}
		if(opt==3)
		{
			LL ans=query_cha(1,from,to);
			LL x_=query_aven(1,from,to);
			LL len=to-from+1;
			print(len*ans-x_*x_,len*len);                                                                                                                                                                                                                                                
			continue;
		}
	}
	return 0;
}
/*
5 4 
1 2 3 4 5 
1 1 2 3 
2 2 4 
3 2 4 
3 1 5
*/

Thinking Bear #1 皇后游戏

【引子】

还记得 NOIP 2012 提高组 Day1 的国王游戏吗？时光飞逝，光阴荏苒，两年过去了。国王游戏早已过时，如今已被皇后游戏取代，请你来解决类似于国王游戏的另一个问题。

【问题描述】

皇后有 n 位大臣，每位大臣的左右手上面分别写上了一个正整数。恰逢国庆节来临，皇后决定为 n 位大臣颁发奖金，其中第 i 位大臣所获得的奖金数目为第 i－1 位大臣所获得奖金数目与前 i 位大臣左手上的数的和的较大值再加上第 i 位大臣右手上的数。形式化地讲：我们设第 i 位大臣左手上的正整数为 ai，右手上的正整数为 bi，则第 i 位大臣获得的奖金数目为 ci可以表达为：

当然,吝啬的皇后并不希望太多的奖金被发给大臣，所以她想请你来重新安排一下队伍的顺序，使得获得奖金最多的大臣，所获奖金数目尽可能的少。注意：重新安排队伍并不意味着一定要打乱顺序，我们允许不改变任何一位大臣的位置。

【输入格式】

第一行包含一个正整数 T，表示测试数据的组数。接下来 T 个部分，每个部分的第一行包含一个正整数 n，表示大臣的数目。
每个部分接下来 n 行中，每行两个正整数，分别为 a i 和 b i ，含义如上文所述。

【输出格式】

共 T 行，每行包含一个整数，表示获得奖金最多的大臣所获得的奖金数目。

【样例输入 1】

1 3 4 1 2 2 1 2
Thinking Bear #1 皇后游戏
第 7 页共 8 页

【样例输出 1】

【样例说明 1】

按照 1、2、3 这样排列队伍，获得最多奖金的大臣获得奖金的数目为 10；
按照 1、3、2 这样排列队伍，获得最多奖金的大臣获得奖金的数目为 9；
按照 2、1、3 这样排列队伍，获得最多奖金的大臣获得奖金的数目为 9；
按照 2、3、1 这样排列队伍，获得最多奖金的大臣获得奖金的数目为 8；
按照 3、1、2 这样排列队伍，获得最多奖金的大臣获得奖金的数目为 9；
按照 3、2、1 这样排列队伍，获得最多奖金的大臣获得奖金的数目为 8。
当按照 3、2、1 这样排列队伍时，三位大臣左右手的数分别为： (1, 2)、(2, 2)、(4, 1) 第 1 位大臣获得的奖金为 1 + 2 = 3；第 2 位大臣获得的奖金为 max{3, 3} + 2 = 5；第 3 为大臣获得的奖金为 max{5, 7} + 1 = 8。

【样例输入 2】

2 5 85 100 95 99 76 87 60 97 79 85 12 9 68 18 45 52 61 39 83 63 67 45 99 52 54 82 100 23 54 99 94 63 100 52 68

【样例输出 2】

528 902
Thinking Bear #1 皇后游戏
第 8 页共 8 页

【数据规模与约定】

所有测试点的数据规模如下：

对于全部测试数据满足：1 ≤ ai, bi ≤ 109。

【特别提示】

由于评测在 Linux 下进行，请 C++选手务必注意 Linux 系统下 rand()函数返回值的取值范围是[0, 231).

Solution

这个和国王的游戏比起来可能没有高精度，但是公式个人感觉是要麻烦一些，考场上没有做出来….qwq。大概就是很普通的贪心，观察到后一个人拿的钱是在钱一个人拿的钱的基础上有所增加，我们如果能保证后面的人拿钱最少那么答案就越小，根据公式贪心，假设前i-2个人都排好队，现在要排第i-1和第i个人：
（注意c的下标意义是和a，b的下标意义不一样）
1.考虑第i-1个人放在前面：
$C_{i-1}=max(C_{i-2} , sum_{i-2}+a_{i-1})+b_{i-1}$
$C_{i}=max(max(C_{i-2},sum_{i-2}+a_{i-1})+b_{i-1},sum_{i-2}+a_{i-1}+a{i})+b_{i}$
2.考虑第i个人放在前面：
$C_{i}=max(max(C_{i-2},sum_{i-2}+a_{i})+b_{i},sum_{i-2}+a_{i}+a{i-1})+b_{i-1}$
我们排序的时候只用比较那种的ci更小就可以了
两个公式有公共部分，化简得到：
1.
$max(a_{i-1}+b_{i-1}+b_{i},a_{i-1}+a_{i}+b_{i})$
2.
$max(a_{i}+b_{i}+b_{i-1},a_{i}+a_{i-1}+b_{i-1})$
这就是排序的标准！！
当然要是想骗分的话还是比较简单的，可以选择多重排序结构，选一个最小答案。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define LL long long
using namespace std;
inline int read(){
    char c=getchar();int rtn=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){rtn=rtn*10+c-'0';c=getchar();}
    return rtn*f;
}
LL c,sum;
struct node{
	LL l,r;
}p[505000];
bool cmp(node a,node b){
	return max(a.l+a.r+b.r,a.l+b.l+b.r)<max(b.l+b.r+a.r,b.l+a.l+a.r);
}
int main()
{
	
	//freopen("game.in","r",stdin);
	//freopen("game.out","w",stdout);
	int T;T=read();
	while(T--)
	{                           
		c=0,sum=0;
		int n;n=read();
		for(register int i=1;i<=n;i++)p[i].l=read(),p[i].r=read();
		sort(p+1,p+1+n,cmp);
		c=p[1].l+p[1].r;sum+=p[1].l;
		for(register int i=2;i<=n;i++)
		{
			sum+=p[i].l;
			c=max(c,sum)+p[i].r;
		}
		printf("%lld\n",c);
	}
	return 0;
}
/*
1 3 
4 1 
2 2 
1 2 
2 
5 
85 100 
95 99 
76 87 
60 97 
79 85 
12 
9 68 
18 45 
52 61 
39 83 
63 67 
45 99 
52 54 
82 100
23 54 
99 94
63 100 
52 68
*/